package test.algorithm;

import org.junit.Test;

import cn.demoncat.util.lang.entity.data.LinkedGraph;

/**
 * 图 - 最短路径
 * 
 * @author 延晓磊
 *
 * @since 2020年7月31日
 */
public class GraphWay {

	@Test
	public void test() {
		 // 图
	    LinkedGraph<String, String, Integer> graph = new LinkedGraph<>();
	    graph.addVertex("A");
	    graph.addVertex("B");
	    graph.addVertex("C");
	    graph.addVertex("D");
	    graph.addVertex("E");
	    graph.addVertex("F");
	    graph.addVertex("G");
	    graph.setEdge("A", "B", 5);
	    graph.setEdge("A", "C", 7);
	    graph.setEdge("A", "G", 2);
	    graph.setEdge("B", "G", 3);
	    graph.setEdge("B", "D", 9);
	    graph.setEdge("C", "E", 8);
	    graph.setEdge("D", "F", 4);
	    graph.setEdge("E", "G", 4);
	    graph.setEdge("E", "F", 5);
	    graph.setEdge("F", "G", 6);
	    // 最短路径 - 迪杰斯特拉
	    LinkedGraph<String, String, Integer>.DijkstraData data = graph.getWaysByDijkstra("G", Integer::sum);
	    System.out.println(data.getWeights());
	    System.out.println(data.getWays());
	    System.out.println(data.getWay("B"));
	    System.out.println(data.getWay("D"));
	    // 最短路径 - 弗洛伊德
	    LinkedGraph<String, String, Integer>.FloydData data2 = graph.getWaysByFloyd(0, Integer::sum);
	    System.out.println(data2.getWeights("G"));
	    System.out.println(data2.getWays("G"));
	    System.out.println(data2.getWay("G","B"));
	    System.out.println(data2.getWay("G","D"));
	}
}
